package leetcode

import kotlinetc.println

//https://leetcode.com/problems/next-permutation/
/**
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

求排列的下一个排列，升序

126345

125346

126354


231

1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431


1 2 3 4 5

1 2 3 4 5 6 7
1 2 3 6 4 7 5
1 2 3 6 5 4 7
规律不是很直观:
简单来说就是从后往前找，一旦前面的数字币后面的数字小 ，那么记录这个小数（A）的下标j
然后再一次从后面往前面找，找到一个比这个小数大的数字（B）,并记录B的下标k，交换A，B
最后j位置以后的数字全部逆序一遍
https://leetcode.com/problems/next-permutation/discuss/301199/C%2B%2B-solution-with-detailed-comments
 */
fun main(args: Array<String>) {

    val nums = intArrayOf(1,5,1)
    nextPermutation(nums)
    nums.asList().println()


}

/**
 * similar [permuteUnique]
 */
//todo
fun nextPermutation(nums: IntArray): Unit {

    val len = nums.size
    var j = 0
    var i = len - 1
    while (i > 0) {
        if (nums[i - 1] < nums[i]) {
            j = i - 1
            var k = len - 1
            while (k > 0 && nums[k] <= nums[i - 1]) k--
            swap(nums, j, k)
            var m = j + 1
            var n = len - 1
            while (m < n) {
                swap(nums, m++, n--)
            }
            return

        }
        i--
    }
    nums.reverse()
}

fun swap(nums: IntArray, former: Int, latter: Int) {
    val tmp = nums[latter]
    nums[latter] = nums[former]
    nums[former] = tmp
}